import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 28779
 * Date: 2023-05-13
 * Time: 19:16
 */
public class Sort {

    /**
     * 插入排序
     * @param array
     */
    private static void InsertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= 0; j--) {
                if(array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序（一般不会考）
     * 时间复杂度为：O(n^1.25 - n^1.5) -> n^1.3
     * 空间复杂度为 :O(1)
     * 稳定性:不稳定排序
     * 整体思想：
     * 1.分组（缩小增量）每组进行插入排序
     * @param array
     */
    private static void ShellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            Shell(gap, array);
        }
    }

    public static void Shell(int gap, int[] array) {
        for(int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for(;j >= 0; j -= gap) {
                if(array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */
    public static void selectSort1(int[] array) {
        for(int i = 0; i < array.length ; i++) {
            int minIndex = i;
            for(int j = i + 1; j < array.length ; j++) {
                if(array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(minIndex, i, array);
        }
    }
    //另外一种选择排序的写法
    private static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int minIndex = left;
            int maxIndex = left;
            for(int i = left + 1; i <=right ;i++ ) {
                if(array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if(array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(minIndex, left, array);
            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(maxIndex, right, array);
            left ++;
            right --;
        }
    }

    private static void swap(int Index, int i, int[] array) {
        int temp = array[i];
        array[i] = array[Index];
        array[Index] = temp;
    }

    public static void main(String[] args) {
        int[] array = {1,5,100,2,4,3,1555,6,7,6};

        System.out.println("---------Insert插入排序----------");
        InsertSort(array);
        System.out.println(Arrays.toString(array));

        System.out.println("-----------Shall希尔排序----------");
        ShellSort(array);
        System.out.println(Arrays.toString(array));

        System.out.println("-------------选择排序1-------------");
        selectSort1(array);
        System.out.println(Arrays.toString(array));


        System.out.println("-------------选择排序2-------------");
        selectSort2(array);
        System.out.println(Arrays.toString(array));

    }
}
